//
// Description: 208. 实现 Trie (前缀树)
// Created by Loading on 2022/7/17.
//

#include <bits/stdc++.h>

using namespace std;

class Trie {
public:
    Trie() : son(26) {

    }

    void insert(string word) {
        auto p = this;
        for (auto c : word) {
            int u = c - 'a';
            if (!p->son[u]) {
                p->son[u] = new Trie;
            }
            p = p->son[u];
        }
        p->isEnd = true;
    }

    bool search(string word) {
        auto p = this;
        for (auto &c : word) {
            int u = c - 'a';
            if (!p->son[u]) {
                return false;
            }
            p = p->son[u];
        }

        return p->isEnd;
    }

    bool startsWith(string prefix) {
        auto p = this;
        for (auto &c : prefix) {
            int u = c - 'a';
            if (!p->son[u]) {
                return false;
            }
            p = p->son[u];
        }

        return true;
    }

private:
    // 孩子节点
    vector<Trie *> son;
    // 是否结尾
    bool isEnd = false;
};

int main() {
    Trie *obj = new Trie();
    obj->insert("apple");
    bool param_2 = obj->search("apple");
    bool param_3 = obj->startsWith("app");

    cout << param_2 << endl;
    cout << param_3 << endl;

    return 0;
}